{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Distance in Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组列表中的最大距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定&nbsp;<code>m</code>&nbsp;个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数&nbsp;<code>a</code>&nbsp;和&nbsp;<code>b</code>&nbsp;之间的距离定义为它们差的绝对值&nbsp;<code>|a-b|</code>&nbsp;。你的任务就是去找到最大距离</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> \n",
    "[[1,2,3],\n",
    " [4,5],\n",
    " [1,2,3]]\n",
    "<strong>输出：</strong> 4\n",
    "<strong>解释：</strong>\n",
    "一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>每个给定数组至少会有 1 个数字。列表中至少有两个非空数组。</li>\n",
    "\t<li><strong>所有</strong>&nbsp;<code>m</code>&nbsp;个数组中的数字总数目在范围 [2, 10000] 内。</li>\n",
    "\t<li><code>m</code>&nbsp;个数组中所有整数的范围在 [-10000, 10000] 内。</li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-distance-in-arrays](https://leetcode.cn/problems/maximum-distance-in-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-distance-in-arrays](https://leetcode.cn/problems/maximum-distance-in-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,5],[1,2,3]]', '[[1],[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1,n2 = len(nums1), len(nums2)\n",
    "        for i in range(n1):\n",
    "            j=bisect_right(nums2, -nums1[i], key=lambda x:-x)-1\n",
    "            if j>=i:\n",
    "                break\n",
    "        else: # no break\n",
    "            return 0\n",
    "\n",
    "        ans=j-i\n",
    "        print(i,j)\n",
    "        for i in range(1, n1):\n",
    "            x=nums1[i]\n",
    "            while j<n2 and nums2[j]>=x:\n",
    "                j+=1\n",
    "            ans = max(ans, j-1-i)\n",
    "            print(i,j,nums1[i],nums2[j-1])\n",
    "            if j==n2:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        index = 0\n",
    "        for idx in range(len(nums2)):\n",
    "            while index<len(nums1) and nums1[index]>nums2[idx]:\n",
    "                index += 1\n",
    "            if index < len(nums1):\n",
    "                    ans = max(ans, idx-index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j < n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j - 1 - i > ans:\n",
    "                ans = j - i - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ret=0\n",
    "        n1,n2=len(nums1),len(nums2)\n",
    "        a,b=0,0\n",
    "        while a<n1 and b<n2:\n",
    "            while b<n2 and nums1[a]<=nums2[b]:\n",
    "                b+=1\n",
    "            ret=max(ret,b-a-1)\n",
    "            a+=1\n",
    "        return ret\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bisect(self, nums, num):\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            if nums[mid] == num:\n",
    "                return mid\n",
    "            if nums[mid] > num:\n",
    "                l = mid + 1\n",
    "            if nums[mid] < num:\n",
    "                r = mid - 1\n",
    "            \n",
    "        return l\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        j = n2 - 1\n",
    "        ret = 0\n",
    "\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                ret = max(ret, j - i)\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j<n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j-i-1 > ans:\n",
    "                ans = j-i-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n, res = len(nums1), len(nums2), 0\n",
    "        for i in range(m):\n",
    "            l, r = i - 1, n\n",
    "            while l + 1 < r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums2[mid] >= nums1[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l == i - 1: continue\n",
    "            res = max(l - i, res)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res=0\n",
    "        last=0\n",
    "        for i in range(len(nums1)):\n",
    "            for j in range(last,len(nums2)):\n",
    "                if nums1[i]<=nums2[j]:\n",
    "                    res=max(res,j-i)\n",
    "                else:\n",
    "                    last=j\n",
    "                    break\n",
    "        return res\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m = len(nums1)\n",
    "        n = len(nums2)\n",
    "        i = 0\n",
    "        distance = 0\n",
    "        for j in range(n):\n",
    "            while i < m and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < m:\n",
    "                distance = max(distance,j - i)\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j<n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j-i-1 > ans:\n",
    "                ans = j-i-1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        max_d = 0\n",
    "        i = 0\n",
    "        for j in range(len(nums2)):\n",
    "            while i < len(nums1) and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < len(nums1):\n",
    "                max_d = max(max_d, j-i)\n",
    "                \n",
    "        return max_d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for j in range(len(nums2)):\n",
    "            while i < len(nums1) and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i != len(nums1):\n",
    "                ans = max(ans, j-i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result = 0\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        for i in range(n1):\n",
    "            left, right = i, n2 - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(nums2[mid] >= nums1[i]):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if(right >= i):\n",
    "                result = max(result, right-i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = j = 0\n",
    "        ans = 0\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "                if i > j:\n",
    "                  j = i\n",
    "                continue\n",
    "            else:\n",
    "                ans = max(ans, j - i)\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            while j<n and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            if j-i-1 > ans:\n",
    "                ans = j-i-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        dis = 0\n",
    "        while i < len(nums1) and j < len(nums2):\n",
    "            if i <= j and nums1[i] <= nums2[j]:\n",
    "                dis = j - i\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1 = len(nums1); n2 = len(nums2)\n",
    "        j = ans = 0\n",
    "        for i in range(n1):\n",
    "            while j < n2 and nums2[j]>= nums1[i]:\n",
    "                j += 1\n",
    "            if j - i - 1 > ans:\n",
    "                ans = j - i - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = j = 0\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        \n",
    "        return max(j - i - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n, res = len(nums1), len(nums2), 0\n",
    "        for i in range(m):\n",
    "            if i > n: continue\n",
    "            l, r = i - 1, n\n",
    "            while l + 1 != r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums2[mid] >= nums1[i]:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l == i - 1: continue\n",
    "            res = max(l - i, res)\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums2)\n",
    "        pre = 0\n",
    "        for i, x in enumerate(nums1):\n",
    "            left, right = min(pre, i), n \n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums2[mid] >= x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, right - i - 1)\n",
    "            pre = min(pre, right)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        # nums1.reverse()\n",
    "        nums2 = nums2[::-1]\n",
    "        n = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            x = bisect_left(nums2, nums1[i])\n",
    "            t = (n2 - x) - i - 1\n",
    "            if t > ans:\n",
    "                ans = t\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        ans = i = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                ans = max(ans, j - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res = 0\n",
    "        pos1, pos2 = 0,0\n",
    "        while pos1<len(nums1) and pos2<len(nums2):\n",
    "            if nums1[pos1] <= nums2[pos2]:\n",
    "                res = max(res, pos2-pos1)\n",
    "                pos2 += 1\n",
    "            else:\n",
    "                pos1 += 1\n",
    "                pos2 = max(pos2, pos1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums1)):\n",
    "            l, r = i, len(nums2) - 1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums2[mid] >= nums1[i]:\n",
    "                    ans = max(ans, mid - i)\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        '''\n",
    "        j一直在增加，所以一直维护一个最大距离就可以，每个数组只用遍历一次\n",
    "        '''\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        ans = 0\n",
    "        p1, p2 = 0, 0\n",
    "        while p1 < m and p2 < n:\n",
    "            while p1 < m and p2 < n and nums1[p1] <= nums2[p2] and p1 <= p2:\n",
    "                ans = max(ans, p2 - p1)\n",
    "                p2 += 1\n",
    "            else:\n",
    "                p2 += 1\n",
    "            p1 += 1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = 0\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        j = n2 - 1\n",
    "        ret = 0\n",
    "\n",
    "        for i in range(n1):\n",
    "            l = 0\n",
    "            r = n2 - 1\n",
    "            while (l < r) :\n",
    "                mid = l + r + 1 >> 1\n",
    "                if (nums2[mid] >= nums1[i]): l = mid\n",
    "                else: r = mid - 1\n",
    "            \n",
    "\n",
    "            if i <= l:\n",
    "                ret = max(ret, l - i)\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        \n",
    "        maxDistance = 0\n",
    "        index = 0\n",
    "        for j in range(len(nums2)):         \n",
    "            maxShortListIndex = min([j+1, len(nums1), len(nums2)])\n",
    "            for i in range(index, maxShortListIndex):\n",
    "                if nums1[i] > nums2[j]:\n",
    "                    index += 1\n",
    "                if nums1[i] <= nums2[j]:\n",
    "                    maxDistance = max([maxDistance, j - i]) \n",
    "                    break      \n",
    "        return maxDistance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n1 = len(nums1)\n",
    "        n2 = len(nums2)\n",
    "        # 从左到右遍历，nums1[i] < nums2[j]\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for j in range(n2):\n",
    "            while i < n1 and nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            if i < n1:\n",
    "                res = max(res, j - i)\n",
    "        return res\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        i = j = 0\n",
    "        n = len(nums1)\n",
    "        m = len(nums2)\n",
    "        while i < n and j < m:\n",
    "            if nums1[i] > nums2[j]:\n",
    "                i += 1\n",
    "            j += 1\n",
    "        return max(0, j - i - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result, m, n, nums2 = 0, len(nums1), len(nums2), nums2[::-1]\n",
    "        for i in range(min(m, n)):\n",
    "            result = max(result, n - bisect_left(nums2, nums1[i]) - 1 - i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result = 0\n",
    "        j = 0\n",
    "        for i in range(len(nums1)):\n",
    "            while j < len(nums2) and nums1[i] <= nums2[j]:\n",
    "                j += 1\n",
    "            dis = j - i - 1\n",
    "            result = max(dis, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums2)\n",
    "        for i, x in enumerate(nums1):\n",
    "            left, right = i, n \n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums2[mid] >= x:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans = max(ans, right - i - 1)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        i = min(len(nums2) - 1, len(nums1) - 1)\n",
    "        max_distance = 0\n",
    "        l, r = i - 1, len(nums2)\n",
    "        while i >= 0:\n",
    "            while l + 1 < r:\n",
    "                m = (l + r) // 2\n",
    "                if nums2[m] >= nums1[i]:\n",
    "                    l = m\n",
    "                else:\n",
    "                    r = m\n",
    "            max_distance = max(max_distance, l - i)\n",
    "            i -= 1\n",
    "            l, r = i - 1, l + 1\n",
    "        return max_distance\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n=len(nums1)\n",
    "        m=len(nums2)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            temp=nums1[i]\n",
    "            left=i\n",
    "            right=m-1\n",
    "            while left<=right:\n",
    "                mid=(left+right)//2\n",
    "                if nums2[mid]>=temp:\n",
    "                    if mid-i>=0:\n",
    "                        ans=max(ans,mid-i)\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        res = 0\n",
    "        tmp = nums2[::-1]\n",
    "        for i,num in enumerate(nums1):\n",
    "            index = bisect.bisect_left(tmp,num)\n",
    "            index = len(nums2)-index\n",
    "            res = max(res,index-i-1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        n = len(nums1)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            left = i\n",
    "            right = len(nums2) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums2[mid] < nums1[i]:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "                ans = max(ans, left - 1 - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        m, n = len(nums1), len(nums2)\n",
    "        l, r = 0, 0\n",
    "        ans = 0\n",
    "        while l < m:\n",
    "            while r < n and nums1[l] <= nums2[r]:\n",
    "                r += 1\n",
    "            ans = max(ans, r - l - 1)\n",
    "            if n - l - 1<= ans:\n",
    "                break\n",
    "            l += 1\n",
    "            r = max(r, l)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n",
    "        result = 0\n",
    "        n1, n2 = len(nums1), len(nums2)\n",
    "        for i in range(n1):\n",
    "            left, right = i, n2 - 1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(nums2[mid] >= nums1[i]):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if(right >= i):\n",
    "                result = max(result, right-i)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        maxv, minv = -inf, inf\n",
    "        for array in arrays:\n",
    "            mina, maxa = array[0], array[-1]\n",
    "            if maxv != inf and minv != inf:\n",
    "                ans = max(ans, abs(maxv - mina), abs(minv - maxa))\n",
    "            maxv, minv = max(maxv, maxa), min(minv, mina)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        min_ = arrays[0][0]\n",
    "        max_ = arrays[0][-1]\n",
    "        result = 0\n",
    "        for idx, arr in enumerate(arrays):\n",
    "            if idx > 0:\n",
    "                result = max(result, abs(arr[0] - max_))\n",
    "                result = max(result, abs(arr[-1] - min_))\n",
    "\n",
    "\n",
    "            min_ = min(arr[0], min_)\n",
    "            max_ = max(arr[-1], max_)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        cur = arrays.pop(0)\n",
    "        min_val, max_val = cur[0], cur[-1]\n",
    "\n",
    "        for cur in arrays:\n",
    "            res = max(res, max_val - cur[0], cur[-1] - min_val)\n",
    "            max_val = max(max_val, cur[-1])\n",
    "            min_val = min(min_val, cur[0])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        n=len(arrays)\n",
    "       #我只需要维护之前的最大值与最小值(因为是绝对值最大)\n",
    "        pre_min,pre_max=arrays[0][0],arrays[0][-1]\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "           a,b=arrays[i][0],arrays[i][-1]\n",
    "           ans=max(ans,abs(a-pre_min),abs(b-pre_min),abs(a-pre_max),abs(b-pre_max))\n",
    "           if a<pre_min: pre_min=a\n",
    "           if b>pre_max: pre_max=b\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        mins = []\n",
    "        maxs = []\n",
    "\n",
    "        for i, a in enumerate(arrays):\n",
    "            min_ = max_ = a[0]\n",
    "            for num in a[1:]:\n",
    "                if num < min_:\n",
    "                    min_ = num\n",
    "                if num > max_:\n",
    "                    max_ = num\n",
    "            arrays[i] = [min_, max_]\n",
    "\n",
    "            if not mins:\n",
    "                mins.append(min_)\n",
    "            elif min_ < mins[0]:\n",
    "                mins = [min_, mins[0]] \n",
    "            elif len(mins) == 1:\n",
    "                mins = [mins[0], min_]\n",
    "            elif min_ < mins[1]:\n",
    "                mins[1] = min_\n",
    "\n",
    "            if not maxs:\n",
    "                maxs.append(max_)\n",
    "            elif max_ > maxs[0]:\n",
    "                maxs = [max_, maxs[0]]\n",
    "            elif len(maxs) == 1:\n",
    "                maxs = [maxs[0], max_]\n",
    "            elif max_ > maxs[1]:\n",
    "                maxs[1] = max_\n",
    "\n",
    "        ret = -1\n",
    "        for min_, max_ in arrays:\n",
    "            if max_ == maxs[0]:\n",
    "                max_ = maxs[1]\n",
    "            else:\n",
    "                max_ = maxs[0]\n",
    "            ret = max(ret, max_ - min_)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        distance=0\n",
    "        self.min=float('inf')\n",
    "        self.max=float('-inf')\n",
    "\n",
    "        \n",
    "        ans=0\n",
    "        for array in arrays:\n",
    "            t_min=float('inf')\n",
    "            t_max=float('-inf')\n",
    "            for i in array:\n",
    "                if i <t_min:\n",
    "                    t_min=i\n",
    "                if i>t_max:\n",
    "                    t_max=i\n",
    "            print(self.max,t_min,t_max,self.min)\n",
    "            ans=max(ans,self.max-t_min,t_max-self.min)\n",
    "            print(ans)\n",
    "            self.max=max(self.max,t_max)\n",
    "            self.min=min(self.min,t_min)\n",
    "    \n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        # sb了，贪心就能解决的问题，不需要全局信息\n",
    "        ret = -1\n",
    "        curmin, curmax = arrays[0][0], arrays[0][-1]\n",
    "        for a in arrays[1:]:\n",
    "            mina, maxa = a[0], a[-1]\n",
    "            ret = max(ret, maxa - curmin, curmax - mina)\n",
    "            curmin = min(curmin, mina)\n",
    "            curmax = max(curmax, maxa)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        min_val = arrays[0][0]\n",
    "        max_val = arrays[0][-1]\n",
    "        max_dist = 0\n",
    "        for array_ in arrays[1:]:\n",
    "            max_dist = max(max_dist, abs(max_val - array_[0]), abs(array_[-1] - min_val))\n",
    "            min_val = min(min_val, array_[0])\n",
    "            max_val = max(max_val, array_[-1])\n",
    "        return max_dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        ret = -1\n",
    "        curmin, curmax = arrays[0][0], arrays[0][-1]\n",
    "        for a in arrays[1:]:\n",
    "            mina, maxa = a[0], a[-1]\n",
    "            ret = max(ret, maxa - curmin, curmax - mina)\n",
    "            curmin = min(curmin, mina)\n",
    "            curmax = max(curmax, maxa)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        minv, maxv = arrays[0][0], arrays[0][-1]\n",
    "\n",
    "        dis = 0\n",
    "\n",
    "        for arr in arrays[1:]:\n",
    "            mint, maxt = arr[0], arr[-1]\n",
    "\n",
    "            dis = max(dis, abs(maxv-mint), abs(maxt-minv))\n",
    "\n",
    "            minv = min(minv, mint)\n",
    "            maxv = max(maxv, maxt)\n",
    "        \n",
    "        return dis\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        if arrays[0][0]<=arrays[1][0]:\n",
    "            min_1 = arrays[0][0]\n",
    "            min_2 = arrays[1][0]\n",
    "            min_idx1 = 0\n",
    "            min_idx2 = 1\n",
    "        else:\n",
    "            min_1 = arrays[1][0]\n",
    "            min_2 = arrays[0][0]\n",
    "            min_idx1 = 1\n",
    "            min_idx2 = 0\n",
    "        \n",
    "        if arrays[0][-1]>=arrays[1][-1]:\n",
    "            max_1 = arrays[0][-1]\n",
    "            max_2 = arrays[1][-1]\n",
    "            max_idx1 = 0\n",
    "            max_idx2 = 1\n",
    "        else:\n",
    "            max_1 = arrays[1][-1]\n",
    "            max_2 = arrays[0][-1]\n",
    "            max_idx1 = 1\n",
    "            max_idx2 = 0\n",
    "        \n",
    "        for idx, ar in enumerate(arrays[2:]):\n",
    "            idx+=2\n",
    "            if ar[0]<=min_1:\n",
    "                min_2 = min_1\n",
    "                min_idx2 = min_idx1\n",
    "                min_1 = ar[0]\n",
    "                min_idx1 = idx\n",
    "            elif ar[0]<=min_2:\n",
    "                min_2 = ar[0]\n",
    "                min_idx2 = idx\n",
    "            if ar[-1]>=max_1:\n",
    "                max_2 = max_1\n",
    "                max_idx2 = max_idx1\n",
    "                max_1 = ar[-1]\n",
    "                max_idx1 = idx\n",
    "            elif ar[-1]>=max_2:\n",
    "                max_2 = ar[-1]\n",
    "                max_idx2 = idx\n",
    "        if min_idx1!=max_idx1:\n",
    "            return max_1-min_1\n",
    "        else:\n",
    "            return max((max_1-min_2), (max_2-min_1))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        maxlist = [array[-1] for array in arrays]\n",
    "        minlist = [array[0] for array in arrays]\n",
    "        a = maxlist.index(max(maxlist))\n",
    "        b = minlist.index(min(minlist))\n",
    "        if a != b: return abs(maxlist[a]-minlist[b])\n",
    "        else:\n",
    "            c = sorted(maxlist)\n",
    "            d = sorted(minlist)\n",
    "            return max(abs(maxlist[a]-d[1]), abs(minlist[b]-c[-2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        arrays = [x for x in arrays if x]\n",
    "        n = len(arrays)\n",
    "        a, b = arrays[0][0], arrays[0][-1]\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            l, r = arrays[i][0], arrays[i][-1]\n",
    "            ans = max(abs(l - b), abs(a - r), ans)\n",
    "            a = min(a, l)\n",
    "            b = max(b, r)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        first_elements = list(set([i[0] for i in arrays]))\n",
    "        last_elements = list(set([i[-1] for i in arrays]))\n",
    "\n",
    "        first_elements.sort()\n",
    "        last_elements.sort(reverse=True)\n",
    "\n",
    "        def inDifferentArray(i, j):\n",
    "            inum, jnum = first_elements[i], last_elements[j]\n",
    "            inum_times, inum_array_index, jnum_times, jnum_array_index = 0, 0, 0, 0\n",
    "            \n",
    "            for array_index, array in enumerate(arrays):\n",
    "                tmp_array = set(array)\n",
    "                if inum in tmp_array:\n",
    "                    inum_times += 1\n",
    "                    inum_array_index = array_index\n",
    "                if jnum in tmp_array:\n",
    "                    jnum_times += 1\n",
    "                    jnum_array_index = array_index\n",
    "            \n",
    "            if inum_times != 1 or jnum_times != 1:\n",
    "                return True\n",
    "            else:\n",
    "                if inum_array_index != jnum_array_index:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "        i, j = 0, 0\n",
    "        while i < len(first_elements) and j < len(last_elements):\n",
    "            if inDifferentArray(i, j):\n",
    "                return abs(first_elements[i]-last_elements[j])\n",
    "            else:\n",
    "                if i+1 < len(first_elements) and j+1 < len(last_elements):\n",
    "                    if abs(first_elements[i+1]-last_elements[j]) > abs(first_elements[i]-last_elements[j+1]):\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        j += 1\n",
    "                elif i+1 < len(first_elements):\n",
    "                    i += 1\n",
    "                elif j+1 < len(last_elements):\n",
    "                    j += 1\n",
    "                else:\n",
    "                    return abs(first_elements[i]-last_elements[j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        max_v = max([max(i) for i in arrays])\n",
    "        max_v_indexs = [i for i,array in enumerate(arrays) if max_v in array]\n",
    "        min_v = min([min(i) for i in arrays])\n",
    "        min_v_indexs = [i for i,array in enumerate(arrays) if min_v in array]\n",
    "        distance = 0\n",
    "        for i, array in enumerate(arrays):\n",
    "            if max_v not in array or (max_v in array and len(max_v_indexs)>1):\n",
    "                distance = max(abs(max_v - array[0]), distance)\n",
    "            if min_v not in array or (min_v in array and len(min_v_indexs)>1):\n",
    "                distance = max(abs(array[-1]-min_v), distance)\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        max_v = max([max(i) for i in arrays])\n",
    "        max_v_indexs = [i for i,array in enumerate(arrays) if max_v in array]\n",
    "        min_v = min([min(i) for i in arrays])\n",
    "        min_v_indexs = [i for i,array in enumerate(arrays) if min_v in array]\n",
    "        distance = 0\n",
    "        for i, array in enumerate(arrays):\n",
    "            if max_v not in array or (max_v in array and len(max_v_indexs)>1):\n",
    "                distance = max(abs(max_v - array[0]), distance)\n",
    "            if min_v not in array or (min_v in array and len(min_v_indexs)>1):\n",
    "                distance = max(abs(array[-1]-min_v), distance)\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        mins, maxs = [arr[0] for arr in arrays], [arr[-1] for arr in arrays]\n",
    "        ans = 0\n",
    "        minn, maxx = [0, 1], [0, 1]\n",
    "        for i in range(len(mins)):\n",
    "\n",
    "            if mins[i] < mins[minn[0]]: minn[0], minn[1] = i, minn[0]\n",
    "            elif mins[i] < mins[minn[1]] and i != minn[0]: minn[1] = i\n",
    "            if maxs[i] > maxs[maxx[0]]: maxx[0], maxx[1] = i, maxx[0]\n",
    "            elif maxs[i] > maxs[maxx[1]] and i != maxx[0]: maxx[1] = i\n",
    "\n",
    "        print(maxx, minn)\n",
    "        if maxx[0] != minn[0]:\n",
    "            return maxs[maxx[0]] - mins[minn[0]]\n",
    "        else:\n",
    "            return max(maxs[maxx[0]] - mins[minn[1]], \\\n",
    "                        maxs[maxx[1]] - mins[minn[0]])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        if len(arrays)==2:\n",
    "            return max(arrays[0][-1]-arrays[1][0],arrays[1][-1]-arrays[0][0])\n",
    "        arrays.sort(key=lambda x:x[0])\n",
    "        res=-1\n",
    "        for i in range(1,len(arrays)):\n",
    "            res=max(res,arrays[i][-1]-arrays[0][0])\n",
    "        return max(res,arrays[0][-1]-arrays[1][0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        min_nums = [x[0] for x in arrays]\n",
    "        max_nums = [x[-1] for x in arrays]\n",
    "        # 1.\n",
    "        max_gap_in_same_arr = max([x[-1] - x[0] for x in arrays])\n",
    "        # 2. \n",
    "        min_num = min(min_nums)\n",
    "        min_nums.remove(min_num)\n",
    "        sec_min_num = min(min_nums)\n",
    "        # 3.\n",
    "        max_num = max(max_nums)\n",
    "        max_nums.remove(max_num)\n",
    "        sec_max_num = max(max_nums)\n",
    "        # 4.\n",
    "        sec_max_gap = max([sec_max_num - min_num, max_num - sec_min_num])\n",
    "        max_gap = max_num - min_num\n",
    "        res = max_gap if max_gap > max_gap_in_same_arr else sec_max_gap\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        min_list = [i[0] for i in arrays]\n",
    "        max_list = [i[-1] for i in arrays]\n",
    "        res = 0\n",
    "        max1 = -float(\"inf\")\n",
    "        max2 = -float(\"inf\")\n",
    "        for i in range(len(max_list)):\n",
    "            if max_list[i] >= max1:\n",
    "                max2 = max1\n",
    "                max1 = max_list[i]\n",
    "            elif max_list[i] > max2:\n",
    "                max2 = max_list[i]\n",
    "        for i in range(len(min_list)):\n",
    "            if max_list[i] == max1:\n",
    "                tmp = max2 - min_list[i]\n",
    "                if tmp > res:\n",
    "                    res = tmp\n",
    "            else:\n",
    "                tmp = max1 - min_list[i]\n",
    "                if tmp > res:\n",
    "                    res = tmp\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        min_list = [i[0] for i in arrays]\n",
    "        max_list = [i[-1] for i in arrays]\n",
    "        res = 0\n",
    "        max1 = -float(\"inf\")\n",
    "        max2 = -float(\"inf\")\n",
    "        for i in range(len(max_list)):\n",
    "            if max_list[i] >= max1:\n",
    "                max2 = max1\n",
    "                max1 = max_list[i]\n",
    "            elif max_list[i] > max2:\n",
    "                max2 = max_list[i]\n",
    "        for i in range(len(min_list)):\n",
    "            if max_list[i] == max1:\n",
    "                tmp = max2 - min_list[i]\n",
    "                if tmp > res:\n",
    "                    res = tmp\n",
    "            else:\n",
    "                tmp = max1 - min_list[i]\n",
    "                if tmp > res:\n",
    "                    res = tmp\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        num_dic = collections.defaultdict(list)\n",
    "        for idx, array in enumerate(arrays):\n",
    "            num_dic[array[0]].append(idx)\n",
    "            num_dic[array[-1]].append(idx)\n",
    "        item_list = sorted(num_dic.items(), key=lambda x: x[0])\n",
    "        # print(item_list)\n",
    "        begin, end = 0, len(item_list)-1\n",
    "        left, right = item_list[begin], item_list[end]\n",
    "        if len(left[1])==1 and len(right[1])==1 and left[1][0]==right[1][0]:\n",
    "            return max(right[0]-item_list[begin+1][0], item_list[end-1][0]-left[0])\n",
    "        else:\n",
    "            return right[0]-left[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "      list1 = []\n",
    "      list2 = []\n",
    "      res = 0\n",
    "      for i in range(len(arrays)):\n",
    "          list1.append(max(arrays[i]))\n",
    "          list2.append(min(arrays[i]))\n",
    "      max1, min1 =list1[0], list2[0]\n",
    "      for i in range(1,len(list1)):\n",
    "          res = max(res, abs(max1-list2[i]),abs(min1-list1[i]))\n",
    "          max1 =max(max1,list1[i])\n",
    "          min1 = min(min1,list2[i])\n",
    "      return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        xmax = [num[-1] for num in arrays]\n",
    "        xmin = [num[0] for num in arrays]\n",
    "        # indxmax = sorted(range(len(xmax)), key = lambda ind: xmax[ind])\n",
    "        # indxmin = sorted(range(len(xmin)), key = lambda ind: xmin[ind])\n",
    "\n",
    "        # if indxmax[-1] != indxmin[0]:\n",
    "        #     maxDistance = xmax[indxmax[-1]]-xmin[indxmin[0]]\n",
    "        # else:\n",
    "        #     maxDistance = max(xmax[indxmax[-2]]-xmin[indxmin[0]],xmax[indxmax[-1]]-xmin[indxmin[1]])\n",
    "\n",
    "        if xmax.index(max(xmax)) != xmin.index(min(xmin)):\n",
    "            maxDistance = max(xmax)-min(xmin)\n",
    "        else:\n",
    "            xmax.sort()\n",
    "            xmin.sort()\n",
    "            maxDistance = max(xmax[-2]-xmin[0],xmax[-1]-xmin[1])\n",
    "        \n",
    "        return(maxDistance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        min_list = []\n",
    "        max_list = []\n",
    "        for i in arrays:\n",
    "            min_list.append(i[0])\n",
    "            max_list.append(i[-1])\n",
    "        min_list.sort()\n",
    "        max_list.sort()\n",
    "        for j in arrays:\n",
    "            if j[0]==min_list[0] and j[-1]==max_list[-1]:\n",
    "                return max(max_list[-2]-min_list[0],max_list[-1]-min_list[1])\n",
    "        return max_list[-1]-min_list[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "      list1 = []\n",
    "      list2 = []\n",
    "      res = 0\n",
    "      for i in range(len(arrays)):\n",
    "          list1.append(max(arrays[i]))\n",
    "          list2.append(min(arrays[i]))\n",
    "      max1, min1 =list1[0], list2[0]\n",
    "      for i in range(1,len(list1)):\n",
    "          res = max(res, abs(max1-list2[i]),abs(min1-list1[i]))\n",
    "          max1 =max(max1,list1[i])\n",
    "          min1 = min(min1,list2[i])\n",
    "      return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "      list1 = []\n",
    "      list2 = []\n",
    "      res = 0\n",
    "      for i in range(len(arrays)):\n",
    "          list1.append(max(arrays[i]))\n",
    "          list2.append(min(arrays[i]))\n",
    "      max1, min1 =list1[0], list2[0]\n",
    "      for i in range(1,len(list1)):\n",
    "          res = max(res, abs(max1-list2[i]),abs(min1-list1[i]))\n",
    "          max1 =max(max1,list1[i])\n",
    "          min1 = min(min1,list2[i])\n",
    "      return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        arr1 = sorted(arrays, key=lambda x: x[0])\n",
    "        arr2 = sorted(arrays, key=lambda x: x[-1], reverse=True)\n",
    "\n",
    "        pos1 = 0\n",
    "        pos2 = -1\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(arr1):\n",
    "            if arr1[i] is arr2[j]:\n",
    "                if abs(arr1[i+1][pos1] - arr2[j][pos2]) >= abs(arr1[i][pos1] - arr2[j+1][pos2]):\n",
    "                    i = i + 1\n",
    "                else:\n",
    "                    j = j + 1\n",
    "\n",
    "            else:\n",
    "                return abs(arr1[i][pos1] - arr2[j][pos2])\n",
    "\n",
    "        return abs(arr1[i][pos1] - arr2[j][pos2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "\n",
    "        mi = sorted(arrays, key=lambda x: x[0])\n",
    "        ma = sorted(arrays, key=lambda x: x[-1], reverse=True)\n",
    "        if ma[0] == mi[0]:\n",
    "            return ma[0][-1] - mi[1][0] if ma[0][-1] - mi[1][0] > ma[1][-1] - mi[0][0] else ma[1][-1] - mi[0][0]\n",
    "        else:\n",
    "            return ma[0][-1] - mi[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        themax=0\n",
    "        arrays1=sorted(arrays)\n",
    "        arrays2=sorted(arrays,key=lambda x:x[-1])[::-1]\n",
    "        l=arrays1[0][0]\n",
    "        r=arrays2[0][-1]\n",
    "        for i in range(1,len(arrays)):\n",
    "            if abs(arrays1[i][-1]-l)>themax:\n",
    "                themax=abs(arrays1[i][-1]-l)\n",
    "            if abs(arrays2[i][0]-r)>themax:\n",
    "                themax=abs(arrays2[i][0]-r)\n",
    "\n",
    "        return themax\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        def maxdistance(current_max,current_min,current_result,new_array):\n",
    "            result_candidate_0 = new_array[-1] - current_min \n",
    "            result_candidate_1 = current_max - new_array[0] \n",
    "            current_max = max(current_max,new_array[-1])\n",
    "            current_min = min(current_min,new_array[0])\n",
    "            current_result = max(max(current_result,result_candidate_0),result_candidate_1)\n",
    "            return current_max,current_min,current_result\n",
    "        non_empty_index = [] \n",
    "        for i , array in enumerate(arrays):\n",
    "            if len(array) > 0:\n",
    "                non_empty_index.append(i)\n",
    "        non_empty_arrays = [arrays[i] for i in non_empty_index] \n",
    "        current_max = max(non_empty_arrays[0][-1],non_empty_arrays[1][-1])\n",
    "        current_min = min(non_empty_arrays[0][0],non_empty_arrays[1][0])\n",
    "        current_result = max(non_empty_arrays[0][-1] - non_empty_arrays[1][0], \n",
    "                            non_empty_arrays[1][-1] - non_empty_arrays[0][0] )\n",
    "        for array in non_empty_arrays[2:]:\n",
    "            current_max,current_min,current_result = maxdistance(current_max,current_min,current_result,array)\n",
    "        return current_result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        arrayMin = []\n",
    "        arrayMax = []\n",
    "        for arr in arrays:\n",
    "            arrayMin.append(min(arr))\n",
    "            arrayMax.append(max(arr))\n",
    "\n",
    "        ans = 0\n",
    "        sortedMax = sorted(arrayMax)\n",
    "\n",
    "        for i in range(len(arrays)):\n",
    "            if arrayMax[i] == sortedMax[-1]:\n",
    "                ans = max(ans, sortedMax[-2] - arrayMin[i])\n",
    "            else:\n",
    "                ans = max(ans, sortedMax[-1] - arrayMin[i])\n",
    "\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        min_dic={}\n",
    "        max_dic={}\n",
    "\n",
    "        for idt in range(len(arrays)):\n",
    "            n=arrays[idt]\n",
    "            min_num=min(n)\n",
    "            max_num=max(n)\n",
    "            if min_dic.get(min_num)==None:\n",
    "                min_dic[min_num]=[idt]\n",
    "            else:\n",
    "                min_dic[min_num].append(idt)\n",
    "            if max_dic.get(max_num)==None:\n",
    "                max_dic[max_num]=[idt]\n",
    "            else:\n",
    "                max_dic[max_num].append(idt)\n",
    "        print(min_dic)\n",
    "        print(max_dic)\n",
    "        min_keys=list(min_dic.keys())\n",
    "        max_keys=list(max_dic.keys())\n",
    "\n",
    "        while min_keys:\n",
    "            min_key=min(min_keys)\n",
    "            max_key=max(max_keys)\n",
    "            if len(min_dic[min_key])==1 and len(max_dic[max_key])==1 and min_dic[min_key]==max_dic[max_key]:\n",
    "                min_keys.remove(min_key)\n",
    "                max_keys.remove(max_key)\n",
    "\n",
    "                new_min=min(min_keys)\n",
    "                new_max=max(max_keys)\n",
    "\n",
    "                if abs(new_min-min_key)>=abs(new_max-max_key):\n",
    "                    min_keys.append(min_key)\n",
    "                else:\n",
    "                    max_keys.append(max_key)\n",
    "            else:\n",
    "                return abs(max_key-min_key)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        n = len(arrays)\n",
    "        arrays.sort(key=lambda x: (x[0], x[-1]))\n",
    "        m1, m2 = arrays[0][0], arrays[0][-1]\n",
    "        result = -1\n",
    "        for i in range(1, n):\n",
    "            c1, c2 = arrays[i][0], arrays[i][-1]\n",
    "            result = max(result, max(abs(m2 - c1), abs(c2 - m1)))\n",
    "            m1 = min(m1, c1)\n",
    "            m2 = max(m2, c2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        a = sorted(arrays, key=lambda x: x[0])\n",
    "        b = sorted(a[1:], key=lambda x: x[-1])\n",
    "        res = b[-1][-1] - a[0][0]\n",
    "\n",
    "        a = sorted(arrays, key=lambda x: x[-1])\n",
    "        b = sorted(a[:-1], key=lambda x: x[0])\n",
    "\n",
    "        res = max(res, a[-1][-1]-b[0][0])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        list1 = arrays\n",
    "        list_min = [list1[i][0] for i in range(len(list1))]\n",
    "        list_max = [list1[i][-1] for i in range(len(list1))]\n",
    "        list_min1 = sorted(list_min)\n",
    "        list_max1 = sorted(list_max)\n",
    "        minum = list_min1[0]\n",
    "        maxnum = list_max1[-1]\n",
    "        if list_min.index(minum) == list_max.index(maxnum):\n",
    "            num1 = list_max1[-1] - list_min1[1]\n",
    "            num2 = list_max1[-2] - list_min1[0]\n",
    "            step = max([num1, num2])\n",
    "        else:\n",
    "            step = maxnum - minum\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        minIndexList = sorted([i for i in range(len(arrays))], key=lambda index:arrays[index][0])\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(arrays)):\n",
    "            maxNum = arrays[i][-1]\n",
    "\n",
    "            if i == minIndexList[0]:\n",
    "                res = max(res, maxNum-arrays[minIndexList[1]][0])\n",
    "            else:\n",
    "                res = max(res, maxNum-arrays[minIndexList[0]][0])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        return self._maxDistance_v2(arrays)\n",
    "\n",
    "    def _maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        !超时\n",
    "        1. 遍历arrays统计每个数组的最大值和最小值\n",
    "        2. 遍历：取最大距离\n",
    "        \"\"\"\n",
    "        mins = []\n",
    "        maxs = []\n",
    "\n",
    "        for array in arrays:\n",
    "            mins.append(array[0])\n",
    "            maxs.append(array[-1])\n",
    "\n",
    "        maxDistance = -float('inf')\n",
    "        n = len(mins)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                else:\n",
    "                    maxDistance = max(maxDistance, maxs[j] - mins[i])\n",
    "\n",
    "        return maxDistance\n",
    "\n",
    "    def _maxDistance_v2(self, arrays: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        1. 统计每个数组的最小值以及全局最小值所在的行\n",
    "        2. 统计每个数组的最大值以及全局最大值所在的行\n",
    "        \"\"\"\n",
    "        globalMin = float('inf')\n",
    "        globalMax = -float('inf')\n",
    "        globalMinIdx = None\n",
    "        globalMaxIdx = None\n",
    "        mins = []\n",
    "        maxs = []\n",
    "        for idx, array in enumerate(arrays):\n",
    "            mins.append(array[0])\n",
    "            if array[0] < globalMin:\n",
    "                globalMin = array[0]\n",
    "                globalMinIdx = idx\n",
    "\n",
    "            maxs.append(array[-1])\n",
    "            if array[-1] > globalMax:\n",
    "                globalMax = array[-1]\n",
    "                globalMaxIdx = idx\n",
    "\n",
    "        maxDistance1 = max(maxs[:globalMinIdx]+\n",
    "                           maxs[globalMinIdx+1:]) - globalMin\n",
    "        maxDistance2 = globalMax - \\\n",
    "            min(mins[:globalMaxIdx]+mins[globalMaxIdx+1:])\n",
    "        return max(maxDistance1, maxDistance2)\n",
    "\n",
    "\n",
    "def main():\n",
    "    arrays = [[1, 2, 3], [4, 5], [1, 2, 3]]\n",
    "    solu = Solution()\n",
    "    maxDistance = solu.maxDistance(arrays)\n",
    "    print(maxDistance)\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        list1 = arrays\n",
    "        list_min = []\n",
    "        list_max = []\n",
    "        for i in list1:\n",
    "            list_min.append(i[0])\n",
    "            list_max.append(i[-1])\n",
    "        list_min1 = sorted(list_min)\n",
    "        list_max1 = sorted(list_max)\n",
    "\n",
    "        minum = list_min1[0]\n",
    "        maxnum = list_max1[-1]\n",
    "        if list_min.index(minum) == list_max.index(maxnum):\n",
    "            num1 = list_max1[-1] - list_min1[1]\n",
    "            num2 = list_max1[-2] - list_min1[0]\n",
    "            step = max([num1, num2])\n",
    "        else:\n",
    "            step = maxnum - minum\n",
    "        return step\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        nums = {}\n",
    "        n = len(arrays)\n",
    "\n",
    "        que = [ [arrays[i][0], arrays[i][-1]] for i in range(n)]\n",
    "\n",
    "        heapq.heapify(que)\n",
    "        maxLength = 0\n",
    "        minNum, maxNum = heapq.heappop(que)\n",
    "        maxLength = float(\"-inf\")\n",
    "        while que:\n",
    "            min_, max_ = heapq.heappop(que)\n",
    "\n",
    "            maxLength = max(abs(min_ - maxNum), abs(minNum - max_), maxLength)\n",
    "            maxNum = max(max_, maxNum)\n",
    "\n",
    "        return maxLength\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        nums = {}\n",
    "        n = len(arrays)\n",
    "\n",
    "        que = [ [arrays[i][0], arrays[i][-1]] for i in range(n)]\n",
    "\n",
    "        heapq.heapify(que)\n",
    "        maxLength = 0\n",
    "        minNum, maxNum = heapq.heappop(que)\n",
    "        maxLength = float(\"-inf\")\n",
    "        while que:\n",
    "            min_, max_ = heapq.heappop(que)\n",
    "\n",
    "            maxLength = max(abs(min_ - maxNum), abs(minNum - max_), maxLength)\n",
    "            maxNum = max(max_, maxNum)\n",
    "\n",
    "        return maxLength\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        lists=[]\n",
    "        for x in arrays:\n",
    "            lists.append(x[0])\n",
    "            lists.append(x[-1])\n",
    "        \n",
    "        slist = sorted(lists)\n",
    "        \n",
    "        a = slist[0]\n",
    "        b = slist[-1]\n",
    "        \n",
    "        loc= lists.index(a)\n",
    "\n",
    "        if b ==lists[loc+1]:\n",
    "            b1 = slist[-2]\n",
    "            a1 = slist[1]\n",
    "            c = b-a1\n",
    "            d = b1-a\n",
    "            if c>=d:\n",
    "                a=a1\n",
    "            else:\n",
    "                b=b1    \n",
    "        return b-a       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        mix = []\n",
    "        temp1 = 10005\n",
    "        temp2 = -10005\n",
    "        for i in range(len(arrays)):\n",
    "            mi = min(arrays[i])\n",
    "            mx = max(arrays[i])\n",
    "            if mx > temp2:\n",
    "                temp2 = mx\n",
    "                idx2 = i\n",
    "            if mi < temp1:\n",
    "                temp1 = mi\n",
    "                idx1 = i\n",
    "            temp2 = max(temp2, mx)\n",
    "            temp1 = min(temp1, mi)\n",
    "            mix.append((mi, mx))\n",
    "        res = 0\n",
    "        for i in range(len(mix)):\n",
    "            if i != idx1:\n",
    "                res = max(res, mix[i][1] - temp1)\n",
    "            if i != idx2:\n",
    "                res = max(res, temp2 - mix[i][0])\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        ls_max = [a[-1] for a in arrays]\n",
    "        ls_min = [b[0] for b in arrays]\n",
    "        ls_dis = list(zip(ls_max, ls_min))\n",
    "        max_item = max(ls_max)\n",
    "        min_item = min(ls_min)\n",
    "        if (max_item, min_item) in ls_dis:\n",
    "            if len([i for i in ls_min if i == min_item]) == 1:\n",
    "                ls_min.remove(min_item)\n",
    "                ls_max.remove(max_item)\n",
    "                return max(max(ls_max)-min_item, max_item-min(ls_min))\n",
    "        return max_item - min_item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        ls_max = [a[-1] for a in arrays]\n",
    "        ls_min = [b[0] for b in arrays]\n",
    "        ls_dis = list(zip(ls_max, ls_min))\n",
    "        max_item = max(ls_max)\n",
    "        min_item = min(ls_min)\n",
    "        if (max_item, min_item) in ls_dis:\n",
    "            if len([i for i in ls_min if i == min_item]) == 1:\n",
    "                ls_min.remove(min_item)\n",
    "                ls_max.remove(max_item)\n",
    "                return max(max(ls_max)-min_item, max_item-min(ls_min))\n",
    "        return max_item - min_item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        ls_max = [max(a) for a in arrays]\n",
    "        ls_min = [min(b) for b in arrays]\n",
    "        ls_dis = list(zip(ls_max, ls_min))\n",
    "        max_item = max(ls_max)\n",
    "        min_item = min(ls_min)\n",
    "        if (max_item, min_item) in ls_dis:\n",
    "            if len([i for i in ls_min if i == min_item]) == 1:\n",
    "                ls_min.remove(min_item)\n",
    "                ls_max.remove(max_item)\n",
    "                return max(max(ls_max)-min_item, max_item-min(ls_min))\n",
    "        return max_item - min_item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        arr = []\n",
    "        for l in arrays:\n",
    "            min_val = min(l)\n",
    "            max_val = max(l)\n",
    "            arr.append((min_val, max_val))\n",
    "\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        def get_min(arr):\n",
    "            min_val = arr[0][0]\n",
    "            min_idx = 0\n",
    "            for i, a in enumerate(arr):\n",
    "                if a[0] < min_val:\n",
    "                    min_val = a[0]\n",
    "                    min_idx = i\n",
    "            return (min_idx, min_val)\n",
    "        def get_max(arr):\n",
    "            max_val = arr[-1][1]\n",
    "            max_idx = len(arr) - 1\n",
    "            for i, a in enumerate(arr):\n",
    "                if a[1] > max_val:\n",
    "                    max_val = a[1]\n",
    "                    max_idx = i\n",
    "            return (max_idx, max_val)\n",
    "        res = []\n",
    "        min_idx, min_val = get_min(arr)\n",
    "        rm_min = list(arr)\n",
    "        rm_min.pop(min_idx)\n",
    "        _, max_val = get_max(rm_min)\n",
    "        res.append(max_val - min_val)\n",
    "\n",
    "        max_idx, max_val = get_max(arr)\n",
    "        rm_max = list(arr)\n",
    "        rm_max.pop(max_idx)\n",
    "        _, min_val = get_min(rm_max)\n",
    "        res.append(max_val - min_val)\n",
    "\n",
    "        print(res)\n",
    "        return max(res)\n",
    "\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        _mins = [arr[0] for arr in arrays]\n",
    "        _maxs = [arr[-1] for arr in arrays]\n",
    "        where_min = _mins.index(min(_mins))\n",
    "        where_max = _maxs.index(max(_maxs))\n",
    "        rx = sorted(_mins + _maxs)\n",
    "\n",
    "        if where_min!=where_max:\n",
    "            return rx[-1] - rx[0]\n",
    "        else:\n",
    "            return max(rx[-2] - rx[0], rx[-1] - rx[1])\n",
    "\n",
    "\n",
    "        # mm = 0\n",
    "        # len_ = len(arrays)\n",
    "        \n",
    "        # for i in range(len_):\n",
    "        #     for j in range(len_):\n",
    "        #         if i == j: continue\n",
    "        #         temp = max(abs(_maxs[i] - _mins[j]), abs(_maxs[j] - _mins[i]))\n",
    "        #         if temp > mm:\n",
    "        #             mm = temp\n",
    "        # return mm\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "#         ansmax = ansmin = 0\n",
    "#         minv, maxv = arrays[0][0], arrays[0][-1]\n",
    "#         for i in arrays[1:]:\n",
    "#             curmin, curmax = i[0], i[-1]\n",
    "#             ansmax, ansmin = max(curmax-minv, ansmax), max(maxv - curmin, ansmin)\n",
    "#             minv, maxv = min(minv,curmin), max(curmax, maxv)\n",
    "#         return max(ansmax, ansmin)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        num_dic = collections.defaultdict(list)\n",
    "        print(num_dic)\n",
    "        for idx, array in enumerate(arrays):\n",
    "            num_dic[array[0]].append(idx)\n",
    "            num_dic[array[-1]].append(idx)\n",
    "        print(num_dic)\n",
    "        print(num_dic.items())\n",
    "        item_list = sorted(num_dic.items(), key=lambda x: x[0])\n",
    "        print(item_list)\n",
    "        begin, end = 0, len(item_list)-1\n",
    "        left, right = item_list[begin], item_list[end]\n",
    "        if len(left[1])==1 and len(right[1])==1 and left[1][0]==right[1][0]:\n",
    "            return max(right[0]-item_list[begin+1][0], item_list[end-1][0]-left[0])\n",
    "        else:\n",
    "            return right[0]-left[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        arr = []\n",
    "        for i, x in enumerate(arrays):\n",
    "            for y in x:\n",
    "                arr.append((y, i))\n",
    "        arr.sort()\n",
    "        if arr[0][1] != arr[-1][1]:\n",
    "            return arr[-1][0] - arr[0][0]\n",
    "        cur = arr[0][1]\n",
    "        a = b = 0\n",
    "        for x in arr:\n",
    "            if x[1] != cur:\n",
    "                a = arr[-1][0] - x[0]\n",
    "                break\n",
    "        for x in arr[::-1]:\n",
    "            if x[1] != cur:\n",
    "                b = x[0] - arr[0][0]\n",
    "                break\n",
    "\n",
    "        return max(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        a = []\n",
    "        for row in arrays:\n",
    "            a.append([min(row), max(row)])\n",
    "        a.sort(key= lambda x: x[0])\n",
    "        down = a[0][0]\n",
    "        up = a[0][1]\n",
    "        for i in range(1, len(a)):\n",
    "            minval, maxval = a[i]\n",
    "            if maxval > up:\n",
    "                up = maxval\n",
    "        if up == a[0][1]:\n",
    "            max1 = max([a[i][1] for i in range(1, len(a))])\n",
    "            min1 = min([a[i][0] for i in range(1, len(a))])\n",
    "            return max(up - min1, max1 - down)\n",
    "        else:\n",
    "            return up - down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        maxes = []\n",
    "        res = 0\n",
    "        for i in range(len(arrays)):\n",
    "            cur = arrays[i]\n",
    "            maxes.append((cur[-1] , i))\n",
    "        maxes.sort()\n",
    "        for i in range(len(arrays)):\n",
    "            if maxes[-1][1] == i:\n",
    "                res = max(res , abs(maxes[-2][0] - arrays[i][0]))\n",
    "            else:\n",
    "                res = max(res , abs(maxes[-1][0] - arrays[i][0]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        minHeap, res = [], 0\n",
    "        for i, arr in enumerate(arrays):\n",
    "            heappush(minHeap, (arr[0], i))\n",
    "        for i, arr in enumerate(arrays):\n",
    "            minNum, index = minHeap[0]\n",
    "            if not (minNum == arr[0] and index == i):\n",
    "                res = max(res, arr[-1] - minNum)\n",
    "            else:\n",
    "                minNum, index = heappop(minHeap)\n",
    "                minNumNext, indexNext = minHeap[0]\n",
    "                res = max(res, arr[-1] - minNumNext)\n",
    "                heappush(minHeap, (minNum, index))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "\n",
    "        xmax = [max(num) for num in arrays]\n",
    "        xmin = [min(num) for num in arrays]\n",
    "        indxmax = sorted(range(len(xmax)), key = lambda ind: xmax[ind])\n",
    "        indxmin = sorted(range(len(xmin)), key = lambda ind: xmin[ind])\n",
    "        print(indxmax)\n",
    "        print(indxmin)\n",
    "\n",
    "        if indxmax[-1] != indxmin[0]:\n",
    "            maxDistance = xmax[indxmax[-1]]-xmin[indxmin[0]]\n",
    "        else:\n",
    "            maxDistance = max(xmax[indxmax[-2]]-xmin[indxmin[0]],xmax[indxmax[-1]]-xmin[indxmin[1]])\n",
    "        return(maxDistance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        tmp = []\n",
    "        # min_value = sorted(lst[0] for lst in arrays, reverse=False)\n",
    "        for lst in arrays:\n",
    "            tmp.append([lst[0], lst[-1]])\n",
    "        \n",
    "        min_value = sorted(tmp, reverse=False)\n",
    "        max_value = sorted(tmp, key=lambda x:x[1], reverse=True)\n",
    "\n",
    "        if min_value[0] == max_value[0]:\n",
    "            cpr = max(max_value[1][1]-min_value[0][0],\n",
    "                      max_value[0][1]-min_value[1][0])\n",
    "            return cpr\n",
    "            \n",
    "        return max_value[0][1]-min_value[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        xmax = [num[-1] for num in arrays]\n",
    "        xmin = [num[0] for num in arrays]\n",
    "        indxmax = sorted(range(len(xmax)), key = lambda ind: xmax[ind])\n",
    "        indxmin = sorted(range(len(xmin)), key = lambda ind: xmin[ind])\n",
    "\n",
    "        if indxmax[-1] != indxmin[0]:\n",
    "            maxDistance = xmax[indxmax[-1]]-xmin[indxmin[0]]\n",
    "        else:\n",
    "            maxDistance = max(xmax[indxmax[-2]]-xmin[indxmin[0]],xmax[indxmax[-1]]-xmin[indxmin[1]])\n",
    "        return(maxDistance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        mx = sorted([(arr[-1],i) for i,arr in enumerate(arrays)])[-2:]\n",
    "        mn = sorted([(arr[0],i) for i,arr in enumerate(arrays)])[:2]\n",
    "        ans = 0\n",
    "        for a,i in mx:\n",
    "            for b,j in mn:\n",
    "                if i != j:\n",
    "                    ans = max(ans,a - b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        m = len(arrays)\n",
    "        nums = []\n",
    "        for i in range(m):\n",
    "            for num in arrays[i]:\n",
    "                nums.append([num, i])\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if nums[0][1] != nums[-1][1]:\n",
    "            return abs(nums[0][0] - nums[-1][0])\n",
    "        left = nums[0][1]\n",
    "        right = nums[-1][1]\n",
    "        i = 0\n",
    "        j = n - 1\n",
    "        while nums[i][1] == right:\n",
    "            i += 1\n",
    "        while nums[j][1] == left:\n",
    "            j -= 1\n",
    "        return max(abs(nums[i][0] - nums[-1][0]), abs(nums[j][0] - nums[0][0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDistance(self, arrays: List[List[int]]) -> int:\n",
    "        mins = [[arr[0], i] for i, arr in enumerate(arrays)]\n",
    "        mins.sort()\n",
    "        res = float('-inf')\n",
    "        for i, arr in enumerate(arrays):\n",
    "            if mins[0][1] != i:\n",
    "                res = max(res, arr[-1] - mins[0][0])\n",
    "            else:\n",
    "                res = max(res, arr[-1] - mins[1][0])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
